package 纯字符串;

import java.util.Stack;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-18
 **/

public class No224基本计算器 {

    /**
     * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
     *
     * 示例 1：
     * 输入：s = "1 + 1"
     * 输出：2
     * 示例 2：
     * 输入：s = " 2-1 + 2 "
     * 输出：3
     * 示例 3：
     * 输入：s = "(1+(4+5+2)-3)+(6+8)"
     * 输出：23
     *  
     * 提示：
     * 1 <= s.length <= 3 * 105
     * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
     * s 表示一个有效的表达式
     */

    public int calculate(String s) {

        char[] arr = s.toCharArray();
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> openIndexStack = new Stack<>();
        char lastC = '+';
        int index = 0;

        while (index < arr.length) {
            char c = arr[index++];
            if (c == ' ') {
                continue;
            }
            if (Character.isDigit(c)) {
                int num = c - '0';

                while (index < arr.length && Character.isDigit(arr[index])) {
                    c = arr[index];
                    num *= 10;
                    num += c - '0';
                    index++;
                }

                if (lastC == '+') {
                    stack.add(num);
                } else {
                    stack.add(-num);
                }
            } else if(c == '(') {
                openIndexStack.add(lastC == '+' ? -1 : -2);
                openIndexStack.add(stack.size());
                lastC = '+';
            } else if (c == ')') {
                // 直到上一个openIndexStack
                Integer pop = openIndexStack.pop();
                Integer pop1 = openIndexStack.pop();
                int num = 0;
                while (stack.size() > pop) {
                    num += stack.pop();
                }
                if (pop1 == -1) {
                    stack.add(num);
                } else {
                    stack.add(-num);
                }
                lastC = '+';
            } else{
                lastC = c;
            }
        }

        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }

        return result;
    }

    public static void main(String[] args) {
        No224基本计算器 n = new No224基本计算器();
        int result = n.calculate("1+1");
        System.out.println(result);
    }

}
